{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shifting Letters II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shiftingLetters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字母移位 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个小写英文字母组成的字符串&nbsp;<code>s</code>&nbsp;和一个二维整数数组&nbsp;<code>shifts</code>&nbsp;，其中&nbsp;<code>shifts[i] = [start<sub>i</sub>, end<sub>i</sub>, direction<sub>i</sub>]</code>&nbsp;。对于每个&nbsp;<code>i</code>&nbsp;，将&nbsp;<code>s</code>&nbsp;中从下标&nbsp;<code>start<sub>i</sub></code>&nbsp;到下标&nbsp;<code>end<sub>i</sub></code>&nbsp;（两者都包含）所有字符都进行移位运算，如果&nbsp;<code>direction<sub>i</sub> = 1</code>&nbsp;将字符向后移位，如果&nbsp;<code>direction<sub>i</sub> = 0</code>&nbsp;将字符向前移位。</p>\n",
    "\n",
    "<p>将一个字符 <strong>向后</strong>&nbsp;移位的意思是将这个字符用字母表中 <strong>下一个</strong>&nbsp;字母替换（字母表视为环绕的，所以&nbsp;<code>'z'</code>&nbsp;变成&nbsp;<code>'a'</code>）。类似的，将一个字符 <strong>向前</strong>&nbsp;移位的意思是将这个字符用字母表中 <strong>前一个</strong>&nbsp;字母替换（字母表是环绕的，所以&nbsp;<code>'a'</code>&nbsp;变成&nbsp;<code>'z'</code>&nbsp;）。</p>\n",
    "\n",
    "<p>请你返回对 <code>s</code>&nbsp;进行所有移位操作以后得到的最终字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"abc\", shifts = [[0,1,0],[1,2,1],[0,2,1]]\n",
    "<b>输出：</b>\"ace\"\n",
    "<b>解释：</b>首先，将下标从 0 到 1 的字母向前移位，得到 s = \"zac\" 。\n",
    "然后，将下标从 1 到 2 的字母向后移位，得到 s = \"zbd\" 。\n",
    "最后，将下标从 0 到 2 的字符向后移位，得到 s = \"ace\" 。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"dztz\", shifts = [[0,0,0],[1,1,1]]\n",
    "<b>输出：</b>\"catz\"\n",
    "<b>解释：</b>首先，将下标从 0 到 0 的字母向前移位，得到 s = \"cztz\" 。\n",
    "最后，将下标从 1 到 1 的字符向后移位，得到 s = \"catz\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length, shifts.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>shifts[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub> &lt;= end<sub>i</sub> &lt; s.length</code></li>\n",
    "\t<li><code>0 &lt;= direction<sub>i</sub> &lt;= 1</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shifting-letters-ii](https://leetcode.cn/problems/shifting-letters-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shifting-letters-ii](https://leetcode.cn/problems/shifting-letters-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abc\"\\n[[0,1,0],[1,2,1],[0,2,1]]', '\"dztz\"\\n[[0,0,0],[1,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        s_len = len(s)\n",
    "        diff = [0]*(s_len+1)\n",
    "        for start, end, direction in shifts:\n",
    "            if direction:\n",
    "                diff[start]+=1\n",
    "                diff[end+1]-= 1\n",
    "            else:\n",
    "                diff[start]-=1\n",
    "                diff[end+1]+= 1\n",
    "        shifts_list = [ord(v)-97 for v in s]\n",
    "        # print(diff)\n",
    "        shifts_list[0] = (shifts_list[0]+diff[0])%26\n",
    "        for i in range(1, s_len):\n",
    "            diff[i]+=diff[i-1]\n",
    "            shifts_list[i] = (shifts_list[i]+diff[i])%26\n",
    "        return ''.join(chr(v+97) for v in shifts_list)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += dir * 2 - 1\n",
    "            diff[end + 1] -= dir * 2 - 1\n",
    "        return ''.join(ascii_lowercase[(c2i[c] + shift) % 26] for c, shift in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        prefix_array = [0] * (len(s)+1)\n",
    "        for start, end, direction in shifts:\n",
    "            counter = 1 if direction == 1 else -1\n",
    "            prefix_array[start]+=counter\n",
    "            prefix_array[end+1]-=counter\n",
    "\n",
    "        for i in range(1, len(prefix_array)):\n",
    "            prefix_array[i]+=prefix_array[i-1]\n",
    "\n",
    "        result = \"\"\n",
    "        for i in range(len(s)):\n",
    "            new_val = (ord(s[i]) + prefix_array[i]%26)\n",
    "            if 97 <= new_val <= 122:\n",
    "                result+=chr(new_val)\n",
    "            elif new_val > 122:\n",
    "                result+=chr(new_val%123 + 97)\n",
    "            else:\n",
    "                result+=chr(new_val+26)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        aord = ord(\"a\")\n",
    "        diffs = [0] * (len(s)+1)\n",
    "        for start, end, dir in shifts:\n",
    "            d = 1 if dir else -1\n",
    "            diffs[start] += d\n",
    "            diffs[end+1] -= d\n",
    "        \n",
    "        # cur = 0\n",
    "        # ans = [\"\"] * n\n",
    "        \n",
    "        # for i in range(n):\n",
    "        #     cur += diffs[i]\n",
    "        #     ans[i] = chr((ord(s[i]) - aord + cur) % 26 + aord)\n",
    "        # return \"\".join(ans)\n",
    "\n",
    "        return \"\".join(chr((ord(c) - aord + d) % 26 + aord) for c,d in zip(s, accumulate(diffs)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        d = [0] * (n+1)\n",
    "        for a,b,c in shifts:\n",
    "            num = 1 if c == 1 else -1\n",
    "            d[a] += num\n",
    "            d[b+1] -= num\n",
    "        sd = 0\n",
    "        ls = list(s)\n",
    "        for i,x,num in zip(range(n),ls,d):\n",
    "            sd += num\n",
    "            ls[i] = chr((ord(x)+sd-ord('a'))%26 + ord('a'))\n",
    "        return ''.join(ls)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, val in shifts:\n",
    "            if val:\n",
    "                diff[start] += 1\n",
    "                diff[end+1] -= 1\n",
    "            else:\n",
    "                diff[start] -= 1\n",
    "                diff[end+1] += 1\n",
    "        \n",
    "        s = list(s)\n",
    "        diff[0] = diff[0] - diff[0] // 26 * 26\n",
    "        s[0] = chr((ord(s[0]) - ord(\"a\") + 26 + diff[0]) % 26 + ord(\"a\"))\n",
    "        for i in range(1, len(s)):\n",
    "            diff[i] += diff[i-1]\n",
    "            diff[i] = diff[i] - diff[i] // 26 * 26\n",
    "            s[i] = chr((ord(s[i]) - ord(\"a\") + 26 + diff[i]) % 26 + ord(\"a\"))\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff=[0]*(len(s)+1)\n",
    "        for i,j,r in shifts:\n",
    "            diff[i]+=2*r-1\n",
    "            diff[j+1]-=2*r-1\n",
    "\n",
    "        for i in range(1,len(s)):\n",
    "            diff[i]+=diff[i-1]\n",
    "\n",
    "        res=[ord(_) for _ in s]\n",
    "        for i in range(len(res)):\n",
    "            cur=res[i]+diff[i]-ord('a')\n",
    "            res[i]=(cur+26)%26+ord('a')\n",
    "        return ''.join([chr(_) for _ in res])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        incdec = [0] * (n + 1)\n",
    "        for i, j, direct in shifts:\n",
    "            incdec[i] += direct * 2 - 1\n",
    "            incdec[j + 1] -= direct * 2 - 1\n",
    "        for i in range(1, n):\n",
    "            incdec[i] += incdec[i - 1]\n",
    "        \n",
    "        a = ord(\"a\")\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            nc = chr((ord(s[i]) - a + incdec[i]) % 26 + a)\n",
    "            ans.append(nc)\n",
    "        return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0]\n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            diff.append(ord(s[i]) - ord(s[i - 1]))\n",
    "\n",
    "        for i in shifts:\n",
    "            if i[0] > 0: diff[i[0]] += 2 * i[2] - 1\n",
    "            if i[1] < n - 1: diff[i[1] + 1] -= 2 * i[2] - 1\n",
    "            if i[0] == 0: diff[0] += 2 * i[2] - 1\n",
    "            \n",
    "        ans = [ord(s[0]) + diff[0]]\n",
    "        for i in range(1, n):\n",
    "            ans.append(ans[i - 1] + diff[i])\n",
    "        return ''.join(chr(97 + (i - 97) % 26) for i in ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        l = [ord(c) for c in s]\n",
    "        diff = [l[0]]\n",
    "\n",
    "        for i in range(len(l)):\n",
    "            if i < len(l) - 1:\n",
    "                diff.append(l[i + 1] - l[i])\n",
    "\n",
    "        diff.append(0)\n",
    "\n",
    "        for start, end, direction in shifts:\n",
    "            if direction == 1:\n",
    "                diff[start] += 1\n",
    "                diff[end + 1] -= 1\n",
    "            else:\n",
    "                diff[start] -= 1\n",
    "                diff[end + 1] += 1\n",
    "\n",
    "        l = list(accumulate(diff))[: -1]\n",
    "        ret = ''.join([chr(97 + (n - 97) % 26) for n in l])\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n =len(s)\n",
    "        diff = [0] * n\n",
    "        for i,j,k in shifts:\n",
    "            diff[i] += (2 * k - 1)\n",
    "            if j + 1 < n:\n",
    "                diff[j + 1] += (-(2 * k - 1))\n",
    "\n",
    "        lst = [diff[0]]\n",
    "        for d in diff[1:]:\n",
    "            lst.append(lst[-1] + d)\n",
    "\n",
    "        ans = list()\n",
    "        for w in s:\n",
    "            ans.append(ord(w) - ord('a'))\n",
    "\n",
    "        word = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        for f in range(n):\n",
    "            ans[f] = word[(ans[f] + lst[f]) % 26]\n",
    "\n",
    "        return ''.join(each for each in ans)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        incdec = [0] * (n + 1)\n",
    "        for i, j, direct in shifts:\n",
    "            if direct == 0:\n",
    "                direct = -1\n",
    "            incdec[i] += direct\n",
    "            incdec[j + 1] -= direct\n",
    "        for i in range(1, n):\n",
    "            incdec[i] += incdec[i - 1]\n",
    "        \n",
    "        a = ord(\"a\")\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            nc = chr((ord(s[i]) - a + incdec[i]) % 26 + a)\n",
    "            ans.append(nc)\n",
    "        return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, src: str, shifts: List[List[int]]) -> str:\n",
    "        table = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        c2i = { c:i for i, c in enumerate(table) }\n",
    "        n = len(src)\n",
    "        diff = [0] * n\n",
    "        for s, e, d in shifts:\n",
    "            change = -1 if d == 0 else 1\n",
    "            diff[s] += change\n",
    "            if e + 1 < n:\n",
    "                diff[e+1] -= change\n",
    "        ans = [''] * n\n",
    "        add = 0\n",
    "        for i in range(n):\n",
    "            add += diff[i]\n",
    "            ci = c2i[src[i]] + add\n",
    "            nc = ((ci%26) + 26)%26\n",
    "            ans[i] = table[nc]\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += dir * 2 - 1\n",
    "            diff[end + 1] -= dir * 2 - 1\n",
    "        return ''.join(ascii_lowercase[(self.c2i[c] + shift) % 26] for c, shift in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * (n + 1)\n",
    "        for i, j, d in shifts:\n",
    "            diff[i] += d * 2 - 1\n",
    "            diff[j+1] -= d * 2 - 1\n",
    "        p = list(accumulate(diff))\n",
    "        return ''.join(chr((p[i] + ord(s[i]) - ord('a')) % 26 + ord('a')) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s)+1)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += dir * 2 - 1\n",
    "            diff[end + 1] -= dir * 2 - 1\n",
    "        res = [0] * len(s)\n",
    "        ans = \"\"\n",
    "        change = 0\n",
    "        for index,data in enumerate(zip(diff,s)):\n",
    "            i,char = data[0],data[1]\n",
    "            change += i\n",
    "            temp = change+ord(char)\n",
    "            while temp<97:\n",
    "                temp = 26 + temp\n",
    "            while temp>122:\n",
    "                temp = temp-26\n",
    "            res[index] = (temp)\n",
    "        char_list = [chr(i) for i in res]\n",
    "        result_string = ''.join(char_list)\n",
    "        # for i in res:\n",
    "        #     i = str(i)\n",
    "        #     ans+=i\n",
    "        return result_string\n",
    "\n",
    "\n",
    "        # #差分数组 转成ord 取余运算\n",
    "        # lis = [ord(i) for i in s]\n",
    "        # # diff = [l[0]] * len(l)\n",
    "        # ans = \"\"\n",
    "        # n = len(lis)\n",
    "        # diff =[lis[i]-lis[i-1] for i in range(1,n)]\n",
    "        # diff = [lis[0]] +diff \n",
    "        # for l,r,v in shifts:\n",
    "        #     if v == 1:\n",
    "        #         diff[l] += 1\n",
    "        #         if r+1<n:\n",
    "        #             diff[r+1] -= 1\n",
    "        #     else:\n",
    "        #         diff[l] -= 1\n",
    "        #         if r+1 < n:\n",
    "        #             diff[r+1] += 1\n",
    "        #     while diff[0]<97:\n",
    "        #         diff[0] = 26 + diff[0]\n",
    "        #     while diff[0]>122:\n",
    "        #         diff[0] = diff[0]-26\n",
    "        # for i in range(1,n):\n",
    "        #     diff[i] += diff[i-1]     \n",
    "        #     while diff[i]<97:\n",
    "        #         diff[i] = 26 + diff[i]\n",
    "        #     while diff[i]>122:\n",
    "        #         diff[i] = diff[i]-26\n",
    "        #     # ans += chr(i)\n",
    "        #     # print(ans)\n",
    "        # for i in diff:\n",
    "        #     ans += chr(i)\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        ans = [''] * len(s)\n",
    "        for i in range(len(shifts)):\n",
    "            diff[shifts[i][0]] += shifts[i][2] if shifts[i][2] == 1 else -1\n",
    "            diff[shifts[i][1] + 1] -= shifts[i][2] if shifts[i][2] == 1 else -1\n",
    "        for i, v in enumerate(accumulate(diff[:-1])):\n",
    "            ans[i] = chr(((ord(s[i]) + v) - 97) % 26 + 97)\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        d = [0] * (len(s)+1)\n",
    "        for start,end,direction in shifts:\n",
    "            if direction == 1 :\n",
    "                d[start] +=1\n",
    "                d[end+1] -=1\n",
    "            elif direction == 0:\n",
    "                d[start]+=-1\n",
    "                d[end+1]-=-1\n",
    "        return ''.join(ascii_lowercase[(c2i[c] + shift) % 26] for c, shift in zip(s, accumulate(d)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * (n + 1)\n",
    "        for i, j, d in shifts:\n",
    "            if d:\n",
    "                diff[i] += 1\n",
    "                diff[j+1] -= 1\n",
    "            else:\n",
    "                diff[i] -= 1\n",
    "                diff[j+1] += 1\n",
    "        p = list(accumulate(diff))\n",
    "        # print(p)\n",
    "        s = list(s)\n",
    "        for i in range(n):\n",
    "            # print(s[i], ord(s[i]))\n",
    "            s[i] = chr((p[i] + ord(s[i]) - ord('a')) % 26 + ord('a'))\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s)+2)\n",
    "        for f, t, x in shifts:\n",
    "            diff[f] += (-1) ** (x+1)\n",
    "            diff[t+1] -= (-1) ** (x+1)\n",
    "        return \"\".join(ascii_lowercase[(c2i[c]+x)%26] for c, x in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        \n",
    "        diff = [0 for _ in range(n)]\n",
    "        \n",
    "        for start, end, d in shifts:\n",
    "            d = 1 if d == 1 else -1\n",
    "            diff[start] += d\n",
    "            if end + 1< n:\n",
    "                diff[end + 1] -= d\n",
    "                \n",
    "        for i in range(1, n):\n",
    "            diff[i] += diff[i - 1]\n",
    "            \n",
    "        res = ['' for _ in range(n)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            res[i] = chr(\n",
    "                (\n",
    "                    ord(s[i]) - ord('a') + diff[i] + 26\n",
    "                ) % 26 + ord('a')\n",
    "            )\n",
    "            \n",
    "        return ''.join(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff=[0]*(len(s)+1)\n",
    "        for start,end,dir in shifts:\n",
    "            dir=dir*2-1\n",
    "            diff[start]+=dir\n",
    "            diff[end+1]-=dir\n",
    "        t=[]\n",
    "        for c,shift in zip(s,accumulate(diff)):\n",
    "            t.append(ascii_lowercase[(c2i[c] + shift) % 26])    \n",
    "        return ''.join(t)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += dir * 2 - 1\n",
    "            diff[end + 1] -= dir * 2 - 1\n",
    "        return ''.join(ascii_lowercase[(c2i[c] + shift) % 26] for c, shift in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, val in shifts:\n",
    "            if val:\n",
    "                diff[start] += 1\n",
    "                diff[end+1] -= 1\n",
    "            else:\n",
    "                diff[start] -= 1\n",
    "                diff[end+1] += 1\n",
    "        \n",
    "        s = list(s)\n",
    "        diff[0] = diff[0] - diff[0] // 26 * 26\n",
    "        s[0] = chr((ord(s[0]) - ord(\"a\") + 26 + diff[0]) % 26 + ord(\"a\"))\n",
    "        for i in range(1, len(s)):\n",
    "            diff[i] += diff[i-1]\n",
    "            diff[i] = diff[i] - diff[i] // 26 * 26\n",
    "            s[i] = chr((ord(s[i]) - ord(\"a\") + 26 + diff[i]) % 26 + ord(\"a\"))\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        incdec = [0 for _ in range(n)]\n",
    "        for i, j, direct in shifts:\n",
    "            if direct == 0:\n",
    "                direct = -1\n",
    "            incdec[i] += direct\n",
    "            if j + 1 < n:\n",
    "                incdec[j + 1] -= direct\n",
    "        for i in range(1, n):\n",
    "            incdec[i] += incdec[i - 1]\n",
    "        \n",
    "        a = ord(\"a\")\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            nc = chr((ord(s[i]) - a + incdec[i]) % 26 + a)\n",
    "            ans.append(nc)\n",
    "        return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        ans = [0]*26\n",
    "        for i in range(26):\n",
    "            ans[i] = chr(i+97)\n",
    "        dict = Counter()\n",
    "        res = list(s)\n",
    "        for st,end,flag in shifts:\n",
    "            if flag==1:\n",
    "                dict[st]+=1\n",
    "                dict[end+1]-=1\n",
    "            else:\n",
    "                dict[st]-=1\n",
    "                dict[end+1]+=1\n",
    "        m = 0\n",
    "        for i,x in enumerate(res):\n",
    "            m += dict[i]\n",
    "            t = ans[(ord(x)-97+m+26)%26]\n",
    "            res[i] = t\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s)+1)\n",
    "        for f, t, x in shifts:\n",
    "            diff[f] += (-1) ** (x+1)\n",
    "            diff[t+1] -= (-1) ** (x+1)\n",
    "        return \"\".join(ascii_lowercase[(c2i[c]+x)%26] for c, x in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        incdec = [0 for _ in range(n)]\n",
    "        for i, j, direct in shifts:\n",
    "            if direct == 0:\n",
    "                direct = -1\n",
    "            incdec[i] += direct\n",
    "            if j + 1 < n:\n",
    "                incdec[j + 1] -= direct\n",
    "        for i in range(1, n):\n",
    "            incdec[i] += incdec[i - 1]\n",
    "        \n",
    "        a = ord(\"a\")\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            nc = chr((ord(s[i]) - a + incdec[i]) % 26 + a)\n",
    "            ans.append(nc)\n",
    "        return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        aord = ord(\"a\")\n",
    "        diffs = [0] * (len(s)+1)\n",
    "        for start, end, dir in shifts:\n",
    "            diffs[start] += dir*2 - 1\n",
    "            diffs[end+1] -= dir*2 - 1\n",
    "        \n",
    "        # cur = 0\n",
    "        # ans = [\"\"] * n\n",
    "        \n",
    "        # for i in range(n):\n",
    "        #     cur += diffs[i]\n",
    "        #     ans[i] = chr((ord(s[i]) - aord + cur) % 26 + aord)\n",
    "        # return \"\".join(ans)\n",
    "\n",
    "        return \"\".join(chr((ord(c) - aord + d) % 26 + aord) for c,d in zip(s, accumulate(diffs)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        temp = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        diff = [0] * len(s)\n",
    "        for a, b, c in shifts:\n",
    "            diff[a] += 2 * c - 1\n",
    "            if b + 1 <= len(s) - 1:\n",
    "                diff[b + 1] -= 2 * c - 1\n",
    "        for i in range(1, len(diff)):\n",
    "            diff[i] += diff[i-1]\n",
    "        ans = [None] * len(s)\n",
    "        for i in range(len(s)):\n",
    "            ans[i] = temp[(ord(s[i]) - ord('a') + diff[i]) % 26]\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0]\n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            diff.append(ord(s[i]) - ord(s[i - 1]))\n",
    "\n",
    "        for i in shifts:\n",
    "            if i[0] > 0: diff[i[0]] = diff[i[0]] + 1 if i[2] == 1 else diff[i[0]] - 1\n",
    "            if i[1] < n - 1: diff[i[1] + 1] = diff[i[1] + 1] - 1 if i[2] == 1 else diff[i[1] + 1] + 1\n",
    "            if i[0] == 0: diff[0] = diff[0] + 1 if i[2] == 1 else diff[0] - 1\n",
    "\n",
    "        ans = [ord(s[0]) + diff[0]]\n",
    "        for i in range(1, n):\n",
    "            ans.append(ans[i - 1] + diff[i])\n",
    "        return ''.join(chr(97 + (i - 97) % 26) for i in ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import ascii_lowercase\n",
    "from itertools import accumulate\n",
    "c2i = {c:i for i,c in enumerate(ascii_lowercase)}\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0]*(len(s)+1)\n",
    "        for start,end,dir in shifts:\n",
    "            diff[start] += 2*dir-1\n",
    "            diff[end+1] -= 2*dir-1\n",
    "        return ''.join(ascii_lowercase[(c2i[c]+shift)%26] for c,shift in zip(s,accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        #一眼差分数组解法\n",
    "        n=len(s)\n",
    "        arr=[ord(i) for i in s]\n",
    "        diff=[arr[0]]\n",
    "        for i in range(1,n):\n",
    "            diff.append(arr[i]-arr[i-1])\n",
    "        for l,r,d in shifts:\n",
    "            if d:\n",
    "                diff[l]+=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]-=1\n",
    "            else:\n",
    "                diff[l]-=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]+=1\n",
    "        res=list(accumulate(diff))\n",
    "        for i in range(n):\n",
    "            while res[i]>122:\n",
    "                res[i]=97+res[i]-123\n",
    "            while res[i]<97:\n",
    "                res[i]=122-(96-res[i])\n",
    "            res[i]=chr(res[i])\n",
    "        print(res)\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        import collections\n",
    "        arr = collections.defaultdict(int)\n",
    "        for start, end, count in shifts:\n",
    "            if count == 1:\n",
    "                arr[start] += 1\n",
    "                arr[end+1] -= 1\n",
    "            elif count == 0:\n",
    "                arr[start] -= 1\n",
    "                arr[end+1] += 1\n",
    "        tmp = 0\n",
    "        res = ''\n",
    "        for i in range(0, len(s)):\n",
    "            if i in arr:\n",
    "                tmp += arr[i]\n",
    "            res += chr(((ord(s[i])-ord('a'))+tmp)%26+ord('a'))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        #一眼差分数组解法\n",
    "        n=len(s)\n",
    "        arr=[ord(i)-97 for i in s]\n",
    "        diff=[arr[0]]\n",
    "        for i in range(1,n):\n",
    "            diff.append(arr[i]-arr[i-1])\n",
    "        for l,r,d in shifts:\n",
    "            if d:\n",
    "                diff[l]+=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]-=1\n",
    "            else:\n",
    "                diff[l]-=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]+=1\n",
    "        res=list(accumulate(diff))\n",
    "        for i in range(n):\n",
    "            res[i]%=26\n",
    "            res[i]=chr(res[i]+97)\n",
    "        print(res)\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        #一眼差分数组解法,利用取模优化时间复杂度。\n",
    "        n=len(s)\n",
    "        arr=[ord(i)-97 for i in s]\n",
    "        diff=[arr[0]]\n",
    "        for i in range(1,n):\n",
    "            diff.append(arr[i]-arr[i-1])\n",
    "        for l,r,d in shifts:\n",
    "            if d:\n",
    "                diff[l]+=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]-=1\n",
    "            else:\n",
    "                diff[l]-=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]+=1\n",
    "        res=list(accumulate(diff))\n",
    "        for i in range(n):\n",
    "            res[i]%=26\n",
    "            res[i]=chr(res[i]+97)\n",
    "        print(res)\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0]\n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            diff.append(ord(s[i]) - ord(s[i - 1]))\n",
    "\n",
    "        for i in shifts:\n",
    "            if i[0] > 0: diff[i[0]] = diff[i[0]] + 1 if i[2] == 1 else diff[i[0]] - 1\n",
    "            if i[1] < n - 1: diff[i[1] + 1] = diff[i[1] + 1] - 1 if i[2] == 1 else diff[i[1] + 1] + 1\n",
    "            if i[0] == 0: diff[0] = diff[0] + 1 if i[2] == 1 else diff[0] - 1\n",
    "\n",
    "        ans = [ord(s[0]) + diff[0]]\n",
    "        for i in range(1, n):\n",
    "            ans.append(ans[i - 1] + diff[i])\n",
    "        return ''.join(chr(97 + (i - 97) % 26) for i in ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * n\n",
    "        for ss, e, d in shifts:\n",
    "            diff[ss] += (1 if d == 1 else -1)\n",
    "            if e+1 < n:\n",
    "                diff[e+1] -= (1 if d == 1 else -1)\n",
    "\n",
    "        d = list(accumulate(diff))\n",
    "\n",
    "        alpha = {}\n",
    "        alpha2 = {}\n",
    "        for i in range(26):\n",
    "            alpha[chr(97+i)] = i\n",
    "            alpha[i] = chr(97+i)\n",
    "        \n",
    "            alpha2[chr(97+i)] = 25 - i\n",
    "            alpha2[25 - i] = chr(97+i)\n",
    "\n",
    "\n",
    "        ans = [0] * n\n",
    "\n",
    "        for i, ss in enumerate(s):\n",
    "            if d[i] >= 0:\n",
    "                new_ss = (alpha[ss] + d[i] % 26) % 26\n",
    "                new_ss = alpha[new_ss]\n",
    "            else:\n",
    "                new_ss = (alpha2[ss] + (-d[i]) % 26) % 26\n",
    "                new_ss = alpha2[new_ss]\n",
    "\n",
    "            ans[i] = new_ss\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += dir * 2 - 1\n",
    "            diff[end + 1] -= dir * 2 - 1\n",
    "        return ''.join(ascii_lowercase[(c2i[c] + shift) % 26] for c, shift in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * (n+1)\n",
    "        for l, r, d in shifts:\n",
    "            d = d*2-1\n",
    "            diff[l] += d\n",
    "            diff[r+1] -= d\n",
    "        \n",
    "        ans = ''\n",
    "        for i in range(n):\n",
    "            ans += chr((ord(s[i]) - 97 + diff[i]) % 26 + 97)\n",
    "            diff[i+1] += diff[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        d = [0] * n\n",
    "        for start, end, direction in shifts:\n",
    "            if direction:\n",
    "                d[start] += 1\n",
    "                if end + 1 < n:\n",
    "                    d[end + 1] -= 1\n",
    "            else:\n",
    "                d[start] -= 1\n",
    "                if end + 1 < n:\n",
    "                    d[end + 1] += 1\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            d[i] += d[i - 1]\n",
    "        \n",
    "        newstr = []\n",
    "        for i in range(n):\n",
    "            newstr.append(\n",
    "                chr\n",
    "                (\n",
    "                    (ord(s[i]) - ord('a') + d[i] + 26) % 26 + ord('a')\n",
    "                )\n",
    "            )\n",
    "        return ''.join(newstr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * (n+1)\n",
    "        for shift in shifts:\n",
    "            a = shift[0]\n",
    "            b = shift[1]\n",
    "            dir = shift[2]\n",
    "            delta = 1 if dir == 1 else -1\n",
    "            diff[a] += delta\n",
    "            diff[b+1] -= delta\n",
    "        \n",
    "        cur = 0\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            cur += diff[i]\n",
    "            new_char = (ord(s[i]) - ord('a') + cur) % 26\n",
    "            res.append(chr(new_char + ord('a')))\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s)+1)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += dir * 2 - 1\n",
    "            diff[end + 1] -= dir * 2 - 1\n",
    "        res = []\n",
    "        ans = \"\"\n",
    "        change = 0\n",
    "        for i,char in zip(diff,s):\n",
    "            change += i\n",
    "            temp = change+ord(char)\n",
    "            while temp<97:\n",
    "                temp = 26 + temp\n",
    "            while temp>122:\n",
    "                temp = temp-26\n",
    "            res.append(temp)\n",
    "        char_list = [chr(i) for i in res]\n",
    "        result_string = ''.join(char_list)\n",
    "        # for i in res:\n",
    "        #     i = str(i)\n",
    "        #     ans+=i\n",
    "        return result_string\n",
    "\n",
    "\n",
    "        # #差分数组 转成ord 取余运算\n",
    "        # lis = [ord(i) for i in s]\n",
    "        # # diff = [l[0]] * len(l)\n",
    "        # ans = \"\"\n",
    "        # n = len(lis)\n",
    "        # diff =[lis[i]-lis[i-1] for i in range(1,n)]\n",
    "        # diff = [lis[0]] +diff \n",
    "        # for l,r,v in shifts:\n",
    "        #     if v == 1:\n",
    "        #         diff[l] += 1\n",
    "        #         if r+1<n:\n",
    "        #             diff[r+1] -= 1\n",
    "        #     else:\n",
    "        #         diff[l] -= 1\n",
    "        #         if r+1 < n:\n",
    "        #             diff[r+1] += 1\n",
    "        #     while diff[0]<97:\n",
    "        #         diff[0] = 26 + diff[0]\n",
    "        #     while diff[0]>122:\n",
    "        #         diff[0] = diff[0]-26\n",
    "        # for i in range(1,n):\n",
    "        #     diff[i] += diff[i-1]     \n",
    "        #     while diff[i]<97:\n",
    "        #         diff[i] = 26 + diff[i]\n",
    "        #     while diff[i]>122:\n",
    "        #         diff[i] = diff[i]-26\n",
    "        #     # ans += chr(i)\n",
    "        #     # print(ans)\n",
    "        # for i in diff:\n",
    "        #     ans += chr(i)\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, direction in shifts:\n",
    "            if direction == 1:\n",
    "                diff[start] += 1\n",
    "                diff[end + 1] -= 1\n",
    "            else:\n",
    "                diff[start] -= 1\n",
    "                diff[end + 1] += 1\n",
    "\n",
    "        ans = ''\n",
    "        cumsum = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            cumsum += diff[i]\n",
    "            ans += chr(((ord(ch) - 97 + cumsum) % 26) + 97)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        shifts.sort()\n",
    "        pos = 0\n",
    "        n = len(s)\n",
    "        m = len(shifts)\n",
    "\n",
    "        ud = [0] * (n + 1)\n",
    "\n",
    "        cost = 0\n",
    "        ret = \"\"\n",
    "        for i in range(n):\n",
    "            while pos < m and shifts[pos][0] <= i:\n",
    "                if shifts[pos][2] == 0:\n",
    "                    ud[shifts[pos][1] + 1] += 1\n",
    "                    cost -= 1\n",
    "                else:\n",
    "                    ud[shifts[pos][1] + 1] -= 1\n",
    "                    cost += 1\n",
    "                pos += 1\n",
    "            cost += ud[i]\n",
    "            ret += chr(ord('a') + (ord(s[i]) - ord('a') + cost) % 26)\n",
    "        return ret\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        flag = [0]*(n+1)\n",
    "        for a,b,d in shifts:\n",
    "            if d==0:\n",
    "                flag[a]-=1\n",
    "                flag[b+1]+=1\n",
    "            else:\n",
    "                flag[a]+=1\n",
    "                flag[b+1]-=1\n",
    "        for i in range(1,n+1):\n",
    "            flag[i]+=flag[i-1]\n",
    "        res = ''\n",
    "        for i in range(n):\n",
    "            nxt = flag[i] % 26\n",
    "            res += chr((ord(s[i])-ord('a') + nxt)%26 + ord('a'))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n=len(s)\n",
    "        d=[0]*(n+1)\n",
    "        for i in range(len(shifts)):\n",
    "            if shifts[i][2]==1:\n",
    "                d[shifts[i][0]]+=1\n",
    "                d[shifts[i][1]+1]-=1\n",
    "            else:\n",
    "                d[shifts[i][0]]-=1\n",
    "                d[shifts[i][1]+1]+=1\n",
    "        cur=0\n",
    "        ret=''\n",
    "        for i in range(n):\n",
    "            cur+=d[i]\n",
    "            ch=cur+ord(s[i])-ord('a')\n",
    "            if ch>=26:\n",
    "                ret+=chr(ch%26+ord('a'))\n",
    "            elif ch<0:\n",
    "                if ch%(-26)!=0:\n",
    "                    ret+=chr(26+ch%(-26)+ord('a'))\n",
    "                else:\n",
    "                    ret+='a'\n",
    "            else:\n",
    "                ret+=chr(ch+ord('a'))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        dif = [0] * (len(s) + 1)\n",
    "        for a, b, c in shifts:\n",
    "            d = 1 if c == 1 else -1\n",
    "            dif[a] += d\n",
    "            dif[b + 1] -= d\n",
    "        ans, p = \"\", 0\n",
    "        for i, c in enumerate(s):\n",
    "            p += dif[i]\n",
    "            ans += chr((ord(c) - ord('a') + p) % 26 + ord('a'))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        pos = [0] * len(s)\n",
    "\n",
    "        for (start, end, shift) in shifts:\n",
    "            pos[start] += 1 if shift == 1 else -1\n",
    "            if end+1 < len(s):\n",
    "                pos[end+1] -= 1 if shift == 1 else -1\n",
    "        \n",
    "        preSum = 0\n",
    "        res = ''\n",
    "        for i in range(len(s)):\n",
    "            preSum += pos[i]\n",
    "            # print(preSum, (ord(s[i]) + preSum - ord('a')) % 26)\n",
    "            res += chr(ord('a') + (ord(s[i]) + preSum - ord('a')) % 26)\n",
    "\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * (n)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += 1 if dir == 1 else -1\n",
    "            if end + 1 < n:\n",
    "                diff[end+1] -= 1 if dir == 1 else -1\n",
    "\n",
    "        ans = [[''] for _ in range(n)]\n",
    "        diff = list(accumulate(diff))\n",
    "        # for i in range(1, n):\n",
    "            # diff[i] += diff[i - 1]\n",
    "\n",
    "        ans = list(chr((ord(s[i]) - ord('a') + diff[i]) % 26 + ord('a')) for i in range(n))\n",
    "\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for left, right, offset in shifts:\n",
    "            diff[left] += offset * 2 - 1\n",
    "            diff[right + 1] -= offset * 2 - 1\n",
    "        \n",
    "        return ''.join(ascii_lowercase[(c2i[i] + shift) % 26] for i, shift in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        # 一维差分数组\n",
    "        n = len(s)\n",
    "        dp = [0] * (n + 1)\n",
    "        for shift in shifts:\n",
    "            if shift[2] == 1:\n",
    "                dp[shift[0] + 1] += 1\n",
    "                if shift[1] + 1 < n:\n",
    "                    dp[shift[1] + 2] -= 1\n",
    "            else:\n",
    "                dp[shift[0] + 1] -= 1\n",
    "                if shift[1] + 1 < n:\n",
    "                    dp[shift[1] + 2] += 1\n",
    "        for _ in range(1, n+1):\n",
    "            dp[_] += dp[_ - 1]\n",
    "        res = ''\n",
    "        for i in range(n):\n",
    "            res += chr((ord(s[i]) - ord('a') + dp[i + 1]) % 26 + ord('a'))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n=len(s)\n",
    "        diff=[0]*(n+1)\n",
    "        for start,end,direct in shifts:\n",
    "            if direct==1:\n",
    "                diff[start]+=1\n",
    "                diff[end+1]-=1\n",
    "            else:\n",
    "                diff[start]-=1\n",
    "                diff[end+1]+=1\n",
    "        ans=\"\"\n",
    "        #print(diff)\n",
    "        nums=[x for x in accumulate(diff)]\n",
    "        #print(nums[:-1])\n",
    "        alph='abcdefghijklmnopqrstuvwxyz'\n",
    "        for i in range(n):\n",
    "            index=alph.index(s[i])+nums[i]\n",
    "            print(index)\n",
    "            ans+=alph[index%26]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        #一眼差分数组解法\n",
    "        n=len(s)\n",
    "        arr=[ord(i)-97 for i in s]\n",
    "        diff=[arr[0]]\n",
    "        for i in range(1,n):\n",
    "            diff.append(arr[i]-arr[i-1])\n",
    "        for l,r,d in shifts:\n",
    "            if d:\n",
    "                diff[l]+=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]-=1\n",
    "            else:\n",
    "                diff[l]-=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]+=1\n",
    "        res=list(accumulate(diff))\n",
    "        for i in range(n):\n",
    "            res[i]%=26\n",
    "            res[i]=chr(res[i]+97)\n",
    "        print(res)\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, s):\n",
    "        self.ori_s = s\n",
    "        self.real_size = len(s)\n",
    "        i = 0\n",
    "        while (1 << i) < self.real_size:\n",
    "            i += 1\n",
    "        \n",
    "        self.space_size = 1 << (i + 1)\n",
    "        self.leave_size = 1 << i\n",
    "\n",
    "        self.update_flag = [False] * self.space_size\n",
    "        self.update_info = [0] * self.space_size\n",
    "        self.cur_info = [0] * self.space_size\n",
    "\n",
    "        for i in range(self.real_size):\n",
    "            self.init(i, i, 0, self.leave_size - 1, 0)\n",
    "    \n",
    "    def init(self, lidx1, ridx1, lidx2, ridx2, idx):\n",
    "        if lidx2 == ridx2:\n",
    "            self.cur_info[idx] = ord(self.ori_s[lidx1]) - ord('a')\n",
    "            return\n",
    "        \n",
    "        midx2 = (lidx2 + ridx2) >> 1\n",
    "        lidx = (idx << 1) | 1\n",
    "        ridx = lidx + 1\n",
    "        if midx2 < lidx1:\n",
    "            self.init(lidx1, ridx1, midx2 + 1, ridx2, ridx)\n",
    "        else:\n",
    "            self.init(lidx1, ridx1, lidx2, midx2, lidx)\n",
    "        \n",
    "        self.cur_info[idx] += ord(self.ori_s[lidx1]) - ord('a')\n",
    "    \n",
    "    def update(self, lidx1, ridx1, lidx2, ridx2, idx, val):\n",
    "        if lidx2 >= lidx1 and ridx2 <= ridx1:\n",
    "            self.cur_info[idx] += (val * (ridx2 - lidx2 + 1))\n",
    "            self.update_flag[idx] = True\n",
    "            self.update_info[idx] += val\n",
    "            if self.update_info[idx] == 0:\n",
    "                self.update_flag[idx] = False\n",
    "            return\n",
    "        \n",
    "        midx2 = (lidx2 + ridx2) >> 1\n",
    "        lidx = (idx << 1) | 1\n",
    "        ridx = lidx + 1\n",
    "        \n",
    "        self.modify(lidx2, ridx2, idx)\n",
    "        if lidx1 <= midx2:\n",
    "            # self.modify(lidx2, midx2, lidx)\n",
    "            self.update(lidx1, ridx1, lidx2, midx2, lidx, val)\n",
    "        \n",
    "        if ridx1 > midx2:\n",
    "            # self.modify(midx2 + 1, ridx2, ridx)\n",
    "            self.update(lidx1, ridx1, midx2 + 1, ridx2, ridx, val)\n",
    "\n",
    "        self.cur_info[idx] = self.cur_info[lidx] + self.cur_info[ridx]\n",
    "    \n",
    "    def modify(self, lidx2, ridx2, idx):\n",
    "        if not self.update_flag[idx]:\n",
    "            return\n",
    "\n",
    "        val = self.update_info[idx]\n",
    "        self.update_flag[idx] = False\n",
    "        self.update_info[idx] = 0\n",
    "        # if val == 0:\n",
    "        #     return \n",
    "\n",
    "        midx2 = (lidx2 + ridx2) >> 1\n",
    "        lidx = (idx << 1) | 1\n",
    "        ridx = lidx + 1\n",
    "\n",
    "        self.cur_info[lidx] += (val * (midx2 - lidx2 + 1))\n",
    "        self.update_flag[lidx] = True\n",
    "        self.update_info[lidx] += val\n",
    "        self.cur_info[ridx] += (val * (ridx2 - midx2))\n",
    "        self.update_flag[ridx] = True\n",
    "        self.update_info[ridx] += val\n",
    "    \n",
    "    def get(self, lidx1, ridx1, lidx2, ridx2, idx):\n",
    "        if lidx2 >= lidx1 and ridx2 <= ridx1:\n",
    "            return self.cur_info[idx]\n",
    "        \n",
    "        midx2 = (lidx2 + ridx2) >> 1\n",
    "        lidx = (idx << 1) | 1\n",
    "        ridx = lidx + 1\n",
    "        \n",
    "        self.modify(lidx2, ridx2, idx)\n",
    "        res = 0\n",
    "        if lidx1 <= midx2:\n",
    "            res += self.get(lidx1, ridx1, lidx2, midx2, lidx)\n",
    "        \n",
    "        if ridx1 > midx2:\n",
    "            res += self.get(lidx1, ridx1, midx2 + 1, ridx2, ridx)\n",
    "\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        # 并查集  错，应该是线段树(Segment Tree)\n",
    "        st = SegmentTree(s)\n",
    "        # print(st.cur_info)\n",
    "\n",
    "        for i in range(len(shifts)):\n",
    "            st.update(shifts[i][0], shifts[i][1], 0, st.leave_size - 1, 0, 1 if shifts[i][2] == 1 else -1)\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            res.append(st.get(i, i, 0, st.leave_size - 1, 0))\n",
    "        \n",
    "        # print(st.cur_info)\n",
    "        # print(res)\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            res[i] = chr((97 + res[i] % 26))\n",
    "\n",
    "\n",
    "        return ''.join(res)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        d = [0] * (n+1)\n",
    "        for l,r,c in shifts:\n",
    "            d[l] += c * 2 - 1\n",
    "            d[r+1] -= c * 2 - 1\n",
    "        t = \"\"\n",
    "        c = 0\n",
    "        for i in range(n):\n",
    "            c += d[i]\n",
    "            t += chr((ord(s[i]) - 97 + c + 26) % 26 + 97)\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * len(s)\n",
    "        \n",
    "        for start, end, direction in shifts:\n",
    "            action = 1 if direction == 1 else -1\n",
    "\n",
    "            diff[start] += action\n",
    "            if end + 1 < len(s):\n",
    "                diff[end + 1] -= action\n",
    "        for i in range(1, len(s)):\n",
    "            diff[i] += diff[i - 1]\n",
    "\n",
    "\n",
    "        return self._shift_string(s, diff)\n",
    "\n",
    "    def _shift_string(self, old_string: str, actions: List[int]) -> str:\n",
    "        results = \"\"\n",
    "        for s, m in zip(old_string, actions):\n",
    "            s2int = ord(s) - ord('a')\n",
    "            s2int = (s2int + m) % 26 + ord('a')\n",
    "            results += chr(s2int)\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        dif = [0] * (len(s) + 1)\n",
    "        for a, b, c in shifts:\n",
    "            d = 1 if c == 1 else -1\n",
    "            dif[a] += d\n",
    "            dif[b + 1] -= d\n",
    "        ans, p = \"\", 0\n",
    "        for i, c in enumerate(s):\n",
    "            p += dif[i]\n",
    "            ans += chr((ord(c) - ord('a') + p) % 26 + ord('a'))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, ss: str, sh: List[List[int]]) -> str:\n",
    "        n=len(ss)\n",
    "        f=[0]*(n+1)\n",
    "        for s,e,d in sh:\n",
    "            if d==1:\n",
    "                f[s]+=1\n",
    "                f[e+1]-=1\n",
    "            else:\n",
    "                f[s]-=1\n",
    "                f[e+1]+=1\n",
    "        for i in range(1,n):\n",
    "            f[i]+=f[i-1]\n",
    "        res=\"\"\n",
    "        for c,k in zip(ss,f):\n",
    "            k%=26\n",
    "            c=ord(c)+k\n",
    "            if c>ord(\"z\"):\n",
    "                c-=26\n",
    "            res+=chr(c)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        chafen = [0]*len(s)\n",
    "        for i in shifts:\n",
    "            left = i[0]\n",
    "            right = i[1]\n",
    "            # 向前移位定义为-1\n",
    "            if i[2] == 0:\n",
    "                chafen[left] -= 1\n",
    "                if right+1 < len(s):\n",
    "                    chafen[right+1] +=1\n",
    "            # 向后移位定义+1\n",
    "            if i[2] == 1:\n",
    "                chafen[left] += 1\n",
    "                if right+1 < len(s):\n",
    "                    chafen[right+1] -= 1\n",
    "        for i in range(1,len(s)):\n",
    "            chafen[i] += chafen[i-1]\n",
    "        # 字母开始移位操作\n",
    "        res = ''\n",
    "        for i in range(len(s)):\n",
    "            if chafen[i] < 0:\n",
    "                ind = ord(s[i]) - ord('a') + 26 +chafen[i]%26\n",
    "                ind = ind%26\n",
    "                res += chr(ind+ord('a'))\n",
    "\n",
    "            if chafen[i] > 0:\n",
    "                ind = ord(s[i])- ord('a') + chafen[i]%26\n",
    "                res += chr(ind%26+ord('a'))\n",
    " \n",
    "            if chafen[i] == 0:\n",
    "                res += s[i]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, ss: str, shifts: List[List[int]]) -> str:\n",
    "        n=len(ss)\n",
    "        d=[0]*(n+1)\n",
    "        for s,e,dire in shifts:\n",
    "            d[s]+=1 if dire==1 else -1\n",
    "            d[e+1]-=1 if dire==1 else -1\n",
    "        move=[i for i in accumulate(d)]\n",
    "        ans=''\n",
    "        for i,x in enumerate(move[:n]):\n",
    "            t=(ord(ss[i])-ord('a')+x)%26+ord('a')\n",
    "            ans+=chr(t)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, ss: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(ss)\n",
    "        \n",
    "        diff = [0]*n\n",
    "        for s, e, d in shifts:\n",
    "            x = 1 if d else -1\n",
    "            diff[s] += x\n",
    "            if e+1<n:\n",
    "                diff[e+1] -= x\n",
    "        for i in range(1, n):\n",
    "            diff[i] += diff[i-1]\n",
    "        \n",
    "        ans = \"\"\n",
    "        for i in range(n):\n",
    "            ans += chr((diff[i]+ord(ss[i])-ord(\"a\"))%26+ord(\"a\"))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s) \n",
    "        diff = [0]*n\n",
    "        for x,y,flag in shifts:\n",
    "            if flag == 1:    \n",
    "                diff[x] += 1\n",
    "                if y+1<n:\n",
    "                    diff[y+1] -=1\n",
    "            else:\n",
    "                diff[x] -= 1\n",
    "                if y+1<n:\n",
    "                    diff[y+1]+=1\n",
    "        d = 0\n",
    "        ans = \"\"\n",
    "        for i in range(n):\n",
    "            d += diff[i]\n",
    "            c = s[i]\n",
    "            ans += chr((ord(c)-ord('a')+d)%26+ord('a'))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(s)\n",
    "        # diff = [0] *n\n",
    "        # for a,b,v in shifts:\n",
    "        #     if v == 1:\n",
    "        #         diff[a] += 1\n",
    "        #         if b+1<n:\n",
    "        #             diff[b+1] -= 1\n",
    "        #     elif v == 0:\n",
    "        #         diff[a] -= 1\n",
    "        #         if b+1<n:\n",
    "        #             diff[b+1] += 1\n",
    "        # # for i in range(1,n): #直接更新diff\n",
    "        # #     diff[i] = diff[i]+diff[i-1]\n",
    "        # res = ['']*n\n",
    "        # for i in range(n):\n",
    "        #     if i>0:\n",
    "        #         diff[i] = diff[i] + diff[i-1]\n",
    "        #     res[i] = chr((ord(s[i])-ord('a')+diff[i])%26 + ord('a'))\n",
    "        # # print(diff)\n",
    "        # return ''.join(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * (n + 1)\n",
    "        for x, y, op in shifts:\n",
    "            if op:\n",
    "                diff[x] += 1\n",
    "                diff[y + 1] -= 1\n",
    "            else:\n",
    "                diff[x] += -1\n",
    "                diff[y + 1] -= -1\n",
    "            # print(diff)\n",
    "        total = 0\n",
    "        ans = \"\"\n",
    "        for i in range(n):\n",
    "            total += diff[i]\n",
    "            val = (ord(s[i]) - 97 + total + 26) % 26 + 97\n",
    "            # print(val)\n",
    "            c = chr(val)\n",
    "            ans += c\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        f = [0] * (len(s) + 1)\n",
    "        for start, end, sign in shifts:\n",
    "            if sign == 1:\n",
    "                f[start] += 1\n",
    "                f[end + 1] -= 1\n",
    "            else:\n",
    "                f[start] += -1\n",
    "                f[end + 1] -= -1\n",
    "        res = ''\n",
    "        for i, n in enumerate(list(accumulate(f))[:-1]):\n",
    "            res += chr((n + ord(s[i]) - 97) % 26 + 97)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        # 感觉是不是看到这种元素是三元素数组的就能考虑拆分数组了\n",
    "\n",
    "        diff = [0] * len(s)\n",
    "\n",
    "        for i in shifts:\n",
    "            '''\n",
    "            if i[2]: k = 1\n",
    "            else: k = -1\n",
    "            '''\n",
    "            # dir * 2 - 1\n",
    "            diff[i[0]] += i[2] * 2 - 1\n",
    "            if i[1] + 1 < len(s): diff[i[1] + 1] -= i[2] * 2 - 1\n",
    "\n",
    "        ans = ''\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if i > 0: diff[i] += diff[i - 1]\n",
    "            ans += chr(ord('a') + (ord(s[i]) - ord('a') + diff[i]) % 26)\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
